<!DOCTYPE html>
<!-- saved from url=(0064)https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESIHelp.htm -->
<html lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  
  <title>VivioJS MESI help</title>
  <link rel="shortcut icon" type="image/x-icon" href="https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/vivio.ico">
  <script src="./VivioJS MESI help_files/funcs.js.下载"></script>
  <script src="./VivioJS MESI help_files/vivio.js.下载"></script>
  <script src="./VivioJS MESI help_files/MESI.js.下载"></script>
  <style>
	.sequence td {
	  padding: 5px;
  	  border: 1px solid black;
  	}
  </style>

</head>
<body style="background-color:#e0e0e0;">
  <script>
        header("MESI Cache Coherency Protocol");
  </script><table style="width:96%; margin-left:2%; margin-top:5px">
  <tbody><tr>
    <td style="background-color:#00902a; font-size:x-large; color:white; padding-left:10px; border-radius:5px 5px 5px 5px;">VivioJS</td>
  </tr>
  <tr style="height:5px;"></tr>
  <tr>
    <td id="subtitle" style="background-color:#c0c0c0; font-variant:small-caps; font-size:large; padding-left:10px; border-radius:5px 5px 5px 5px;">MESI Cache Coherency Protocol</td>
  </tr>
</tbody></table>

  <table style="margin-left:2%; width:96%; border:0; border-spacing:0; padding:0;">
    <tbody><tr>
      <td>
        <p style="text-align:justify;"><br>
        This VivioJS animation is designed to help you understand the MESI cache coherency protocol.</p>
        <p style="text-align:justify;">A multiprocessor system is depicted comprising 3 CPUs with local caches and main memory. For simplicity, main memory
        comprises 4 locations a0, a1, a2 and a3. The caches are direct mapped and contain two sets. The even addresses (a0 and a2) map to set 0 whilst the odd
        addresses (a1 and a3) map to set 1.</p>
        <p style="text-align:justify;">NB: in order to simplify this animation, the size of a cache line and that of a CPU read/write operation are identical.
        On a write miss, however, the CPU reads memory even though it will completely overwrite the cache line. This simulates the behaviour of real caches
        where the size of the cache line is usually larger than that of a CPU read/write operation.</p>
      </td>
    </tr>
    <tr>
      <td style="text-align:center; color:red;">
        <div style="position:relative;">
          <!-- tabindex needed for keyboard input -->
          <canvas id="canvas" style="width: 95%; height: 620px; overflow: hidden; display: block; z-index: 0;" width="811" height="620">
            No canvas support
          </canvas>
        <canvas width="811" height="620" style="width: 95%; height: 620px; position: absolute; z-index: 1000; pointer-events: none; overflow: hidden; display: block; left: 0px; top: 0px;"></canvas></div>Click on diagram to activate animation or <a href="https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESI.htm">here</a> for a full screen version.
      </td>
    </tr>
    <tr>
      <td>
        <p style="text-align:justify;">Each CPU contains buttons which initiate read or write transactions on the specified memory location. A "CPU write"
        writes an incrementing value (initially 1) to "memory".</p>
        <p style="text-align:justify;">The idea is to press the buttons and see if you can follow the actions and state transitions which occur. It is possible
        to introduce bugs into the animation by pressing the "bug free" button in the top right hand corner. See if you can determine what the bugs are!</p>
        <p style="text-align:justify;">The direction of the traffic on the address and data busses are indicated by blue and red arrows respectively. The cache
        lines and memory location involved in the transaction are coloured green. Stale memory locations are coloured gray.</p>
        <p style="text-align:justify;">A cache line can be in one of 4 states. <b>INVALID:</b> cache line NOT present in cache. <b>EXCLUSIVE:</b> cache line
        present in this cache ONLY and identical to copy in memory. <b>MODIFIED:</b> cache line present in this cache ONLY and memory copy out of date (stale).
        <b>SHARED:</b> cache line in this cache and possibly other caches, ALL copies identical to memory copy. Writes to <b>SHARED</b> cache lines are write
        through whereas writes to <b>EXCLUSIVE</b> cache lines are write-back. If a cache observes a bus transaction for an address which it contains, it
        asserts the SHARED bus line. MESI is an invalidate cache coherency protocol.</p>
        <p style="text-align:justify;">Here is the state transition diagram for a cache line:</p>
        <p><img style="margin:0px auto; display:block; border:0;" src="./VivioJS MESI help_files/MESI.png" alt="MESI state transition digram"></p>
        <div style="color:red; font-size:larger;">
          <u>Sample sequence to try [from RESET]</u><br>
        </div><br>
        <div>
          <table class="sequence" style="margin-left:2%; width:96%;">
            <tbody><tr>
              <td style="width:5%; text-align:center;">1</td>
              <td style="width:20%;">CPU0: read a0</td>
              <td><i>CPU0 reads a0 from memory <span style="color:red;">[not shared]</span> - state E</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">2</td>
              <td style="width:20%;">CPU0: read a0</td>
              <td><i>CPU0 reads a0 from cache - state E</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">3</td>
              <td style="width:20%;">CPU0: write a0</td>
              <td><i>CPU0 updates a0 in cache ONLY - state M</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">4</td>
              <td style="width:20%;">CPU0: write a0</td>
              <td><i>CPU0 updates a0 in cache ONLY - state M</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">5</td>
              <td style="width:20%;">CPU1: read a0</td>
              <td><i>CPU1 reads a0, CPU0 cache intervenes and supplies data to cache and memory - state S</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">6</td>
              <td style="width:20%;">CPU1: write a0</td>
              <td><i>CPU1 updates a0 in cache and memory and invalidates all other caches with address a0 - state E</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">7</td>
              <td style="width:20%;">CPU1: write a0</td>
              <td><i>CPU1 updates a0 in cache ONLY - state M</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">8</td>
              <td style="width:20%;">CPU0: write a0</td>
              <td><i>CPU0 reads a0, CPU1 cache intervenes and supplies data to cache and memory (S), CPU0 then writes to a0 in cache and memory invalidating
              all other caches with address a0 - state</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">9</td>
              <td style="width:20%;">CPU0: write a2</td>
              <td><i>CPU0 reads a2 from memory (E) and then writes to a2 - state M</i></td>
            </tr>
            <tr>
              <td style="width:5%; text-align:center;">10</td>
              <td style="width:20%;">CPU0: write a0</td>
              <td><i>CPU0 flushes a2 to memory, reads a2 from memory (E) and then writes to a0 - state M</i></td>
            </tr>
          </tbody></table>
        </div>
      </td>
    </tr>
  </tbody></table><br>
  <script>
	vplayer = new VPlayer("canvas", MESI);
	footer("caches");
  </script><table style="width:96%; margin-left:2%; border-spacing:0">
  <tbody><tr style="font-size:small;">
    <td id="count" ;="" style="width:33%; background-color:#00902a; color:white; padding-left:10px; border-radius:5px 0px 0px 5px;">107,419 hits since Jul-05  4.062 secs</td>
    <td style="width:33%; background-color:#00902a; text-align:center; color:white;">Copyright © 2021 jones@scss.tcd.ie</td>
    <td style="text-align:right; background-color:#00902a; color:white; padding-right:10px; border-radius: 0px 5px 5px 0px">last updated: 17-Jul-21</td>
  </tr>
</tbody></table>
<br>



</body></html>